package com.programmercarl.stackandqueue;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/sliding-window-maximum/description/
 *
 * @author yulongtian
 * @create 2024-12-16 10:50
 */
public class Test03 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, 1, 2, 0, 5}, 3)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if (i >= k - 1) {
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }

    /**
     * 自己写的有问题
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        // 初始化队列
        for (int i = 0; i < k; i++) {
            // 保证队列单调，从小到大   last -> first  小 -> 大      入口last 出口first
            if (deque.isEmpty()) {
                deque.addLast(nums[i]);
                continue;
            }
            if (nums[i] >= deque.getLast()) {
                while (!deque.isEmpty() && nums[i] >= deque.getLast()) {
                    deque.pollLast();
                }
            }
            deque.addLast(nums[i]);
        }
        res[index++] = deque.getFirst();
        for (int i = k; i < nums.length; i++) {
            //判断是否移除元素
            if (deque.getFirst() == nums[i - k]) {
                deque.pollFirst();
            }
            //追加元素
            if (nums[i] >= deque.getLast()) {
                while (!deque.isEmpty() && nums[i] >= deque.getLast()) {
                    deque.pollLast();
                }
            }
            deque.addLast(nums[i]);

            res[index++] = deque.getFirst();
        }

        return res;
    }
}
